package weekMatch.two_105;

import java.util.*;

public class LeeCode_04 {
    public static void main(String[] args) {
//        System.out.println(canTraverseAllPairs(new int[]{2, 3, 6}));
        System.out.println(canTraverseAllPairs(new int[]{4,3,12,8}));
    }
    private static boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            getAll(map, nums[i], i);
        }
        for (Integer key : map.keySet()) {
            List<Integer> list = map.get(key);
            for (int i = 0; i < list.size() - 1; i++) {
                union(p, list.get(i), list.get(i + 1));
            }
        }
        int root = find(p, 0);
        for (int i = 1; i < n; i++) {
            if (find(p, i) != root)
                return false;
        }
        return true;
    }
    private static void getAll(Map<Integer, List<Integer>> map, int num, int i){
        int j = 2;
        if (isZhi(num)){
            if (map.containsKey(num)){
                map.get(num).add(i);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(num, list);
            }
            return;
        }
        while (j * j <= num){
            if (num % j == 0 && isZhi(j)){
                if (map.containsKey(j)){
                    map.get(j).add(i);
                }else {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    map.put(j, list);
                }
                getAll(map, num / j, i);
                break;
            }
            j++;
        }
    }
    private static boolean isZhi(int n){
        if (n == 1)
            return false;
        int i = 2;
        while (i * i <= n){
            if (n % i == 0){
                return false;
            }
            i++;
        }
        return true;
    }
    private static int find(int[] p, int x){
        if (p[x] != x)
            p[x] = find(p, p[x]);
        return p[x];
    }
    private static void union(int[] p, int x, int y){
        int rx = find(p, x);
        int ry = find(p, y);
        p[rx] = ry;
    }
    private static int gcd(int x, int y){
        while (x != 0){
            int tmp = x;
            x = y % x;
            y = tmp;
        }
        return y;
    }
}
